home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / prep / semanopt.c < prev   
Encoding:
C/C++ Source or Header  |  1992-08-27  |  13.9 KB  |  545 lines
  1. /*
  2.  *  This file contains routines to perform semantic optimization for
  3.  *  versions (i.e, union queries that pertain to versions).
  4.  *  As such, heuristics used to govern the optimization are applicable
  5.  *  only to the current implementation of versions, and should not be 
  6.  *  used as a general purpose semantic optimizer.
  7.  *
  8.  *  $Header: /private/postgres/src/planner/prep/RCS/semanopt.c,v 1.12 1991/11/18 17:29:14 mer Exp $
  9.  */
  10.  
  11. #include <stdio.h>
  12. #include <strings.h>
  13. #include "tmp/c.h"
  14.  
  15. #include "nodes/nodes.h"
  16. #include "nodes/pg_lisp.h"
  17. #include "nodes/execnodes.h"
  18. #include "nodes/plannodes.h"
  19. #include "nodes/plannodes.a.h"
  20. #include "nodes/primnodes.h"
  21. #include "nodes/primnodes.a.h"
  22. #include "nodes/relation.h"
  23. #include "nodes/relation.a.h"
  24.  
  25. #include "parser/parse.h"
  26. #include "parser/parsetree.h"
  27. #include "tmp/utilities.h"
  28. #include "tmp/datum.h"
  29. #include "utils/log.h"
  30. #include "utils/lsyscache.h"
  31.  
  32. #include "planner/internal.h"
  33. #include "planner/plancat.h"
  34. #include "planner/planner.h"
  35. #include "planner/prepunion.h"
  36. #include "planner/clauses.h"
  37. #include "planner/semanopt.h"
  38.  
  39. /*
  40.  *  SemantOpt:
  41.  * 
  42.  *  Given a tlist and qual pair, routine runs through the 
  43.  *  qualification and substitute all redundent clauses.  Eg:
  44.  *
  45.  *   TClause : tautological clauses  (A.oid = A.oid) becomes (1=1)
  46.  *   CClause : contradictory clauses (A.oid = B.oid where A != B)
  47.  *             becomes where 1=2
  48.  *   EClause : clauses that causes an unwanted existential query.
  49.  *             Clauses that have no link back to the targetlist
  50.  *             defaults to true (i.e., 1=1).
  51.  *             THEREFORE, this will only work for AND clauses.
  52.  *
  53.  *   We cannot simply remove CClauses and EClauses from the qualification
  54.  *   because then any boolean operations done on the qualification may
  55.  *   result in the wrong answer.
  56.  *   
  57.  *   HOWEVER, I have included a very simplistic heuristic to remove
  58.  *   queries with only "and" clauses which have a CClause in them.
  59.  *   The routine will punt if it sees any "not" or "or" clauses.
  60.  *   In the future, it should also handle those two clauses.
  61.  *   I'm going to integrate this is semantop.
  62.  *   
  63.  *
  64.  *  Returns the optimized qual.
  65.  */
  66.  
  67. List
  68. SemantOpt(varlist,rangetable, qual, is_redundent,is_first)
  69.      List varlist,rangetable, qual;
  70.      List *is_redundent;
  71.      int is_first;
  72. {
  73.   static int punt;
  74.   char *attname;
  75.   List retqual = LispNil;
  76.   Index leftvarno = 0;
  77.   Index rightvarno = 0;
  78.   ObjectId op = 0;
  79.   List tmp_list = LispNil;
  80.   List i = LispNil;
  81.  
  82.   /*
  83.    *   NOTE:  Routine doesn't handle func clauses.
  84.    */
  85.  
  86.   if (is_first)
  87.     punt = 0;  /* to initialize the static variable */
  88.  
  89.   retqual = qual;
  90.  
  91.   if (null(qual))
  92.     return(LispNil);
  93.   else
  94.     if (is_clause(qual)) {
  95.       /* At this stage, union vars are existential */
  96.       if (consp(get_leftop(qual)))
  97.     retqual = MakeTClause();
  98.       else {
  99.     op = get_opno((Oper)get_op(qual));
  100.     if (op == 627) {
  101.       leftvarno = get_varno(get_leftop(qual));
  102.       rightvarno = ConstVarno(rangetable,(Const)get_rightop(qual),&attname);
  103.       /*
  104.        *  test for existential clauses first 
  105.        */
  106.       if (!member(lispInteger(leftvarno),varlist) &&
  107.           !member(lispInteger(rightvarno),varlist))
  108.         retqual = MakeTClause();
  109.       else 
  110.         if (leftvarno == rightvarno) {
  111.           retqual = MakeFClause();
  112.           *is_redundent = LispTrue;
  113.         } 
  114.         else
  115.           if (rightvarno > 0 && 
  116.           strcmp(attname,"oid") == 0) {
  117.         List rte1 = LispNil;
  118.         List rte2 = LispNil;
  119.         
  120.         rte1 = nth(leftvarno -1, rangetable);
  121.         rte2 = nth(rightvarno -1, rangetable);
  122.  
  123.         if (CInteger(CADR(CDR(rte1))) != CInteger(CADR(CDR(rte2))))
  124.           retqual = MakeTClause();
  125.           }
  126.     } else 
  127.       if (op == 558) {  /* oid = */
  128.         AttributeNumber leftattno;
  129.         AttributeNumber rightattno;
  130.         List rte1 = LispNil;
  131.         List rte2 = LispNil;
  132.       
  133.         leftvarno = get_varno(get_leftop(qual));
  134.         rightvarno = get_varno(get_rightop(qual));
  135.         leftattno = get_varattno(get_leftop(qual));
  136.         rightattno = get_varattno(get_rightop(qual));
  137.         
  138.         if (!member(lispInteger(leftvarno),varlist) &&
  139.         !member(lispInteger(rightvarno),varlist))
  140.           retqual = MakeTClause();    
  141.         else {
  142.           if (leftattno < 0 && rightattno < 0) {
  143.         /* Comparing the oid field of 2 rels */
  144.         if (leftvarno == rightvarno)
  145.           retqual = MakeTClause();
  146.         else {
  147.           rte1 = nth (leftvarno -1, rangetable);
  148.           rte2 = nth (rightvarno -1, rangetable);
  149.           
  150.           if (strcmp(CString(CADR(rte1)),
  151.                  CString(CADR(rte2))) != 0) {
  152.             retqual = MakeFClause();
  153.             *is_redundent = LispTrue;
  154.           }
  155.         }
  156.           }
  157.         }
  158.       } else 
  159.         /* Just a normal op clause, check to see if it is existential */
  160.         if (IsA(get_leftop(qual),Var)) {
  161.           leftvarno = get_varno(get_leftop(qual));
  162.           if (IsA(get_rightop(qual),Var)) {
  163.         rightvarno = get_varno(get_rightop(qual));
  164.         if (!member(lispInteger(leftvarno),varlist) &&
  165.             !member(lispInteger(rightvarno),varlist))
  166.           retqual = MakeTClause();    /* this is true only for ANDS */
  167.           }
  168.           if (!member(lispInteger(leftvarno),varlist))
  169.         retqual = MakeTClause();
  170.         }
  171.       }
  172.     } else  
  173.       if (and_clause (qual)) {
  174.     foreach(i,get_andclauseargs(qual)) {
  175.       tmp_list = nappend1(tmp_list,SemantOpt(varlist,
  176.                          rangetable, 
  177.                          CAR(i),
  178.                          is_redundent,
  179.                          0));
  180.     }
  181.     retqual = make_andclause(tmp_list);
  182.       }
  183.       else
  184.     if (or_clause (qual)) {
  185.       punt = 1;
  186.       foreach(i,get_orclauseargs(qual)) {
  187.         tmp_list = nappend1(tmp_list,SemantOpt(varlist,
  188.                            rangetable, 
  189.                            CAR(i),
  190.                            is_redundent,
  191.                            0));
  192.       }
  193.       retqual = make_orclause(tmp_list);
  194.     }
  195.     else
  196.       if (not_clause (qual)) {
  197.         punt = 1;
  198.         retqual = make_notclause(SemantOpt(varlist, 
  199.                            rangetable, 
  200.                            get_notclausearg(qual),
  201.                            is_redundent,
  202.                            0));
  203.       }
  204.   if (punt)
  205.     *is_redundent = LispNil;
  206.  
  207.   return (retqual);
  208.   
  209. }
  210.  
  211. /*
  212.  * SemantOpt2 optimizes redundent joins.
  213.  *
  214.  *  The theory behind this is that given to primary keys, eg OIDs
  215.  *  a qual. of the form : 
  216.  *   ... from e in emp where e.oid = emp.oid
  217.  *   can be optimized into scan on emp, instead of a join.
  218.  */
  219. List 
  220. SemantOpt2(rangetable,qual,modqual,tlist)
  221.      List rangetable,qual,modqual,tlist;
  222. {
  223.   AttributeNumber leftattno = 0;
  224.   AttributeNumber rightattno = 0;
  225.   List rte1 = LispNil;
  226.   List rte2 = LispNil;
  227.   Index leftvarno = 0;
  228.   Index rightvarno = 0;
  229.   List i = LispNil;
  230.  
  231.   if (null(qual))
  232.     return(LispNil);
  233.   else
  234.     if (is_clause(qual) && get_opno((Oper)get_op(qual)) == 558) {
  235.       /*
  236.        *  Now to test if they are the same relation.
  237.        */
  238.  
  239.       leftvarno = get_varno(get_leftop(qual));
  240.       rightvarno = get_varno(get_rightop(qual));
  241.       leftattno = get_varattno(get_leftop(qual));
  242.       rightattno = get_varattno(get_rightop(qual));
  243.  
  244.       if (leftattno < 0 && rightattno < 0) {
  245.     /* Comparing the oid field of 2 rels */
  246.     
  247.     rte1 = nth(leftvarno - 1, rangetable);
  248.     rte2 = nth(rightvarno - 1, rangetable);
  249.  
  250.     if (strcmp(CString(CADR(rte1)),
  251.            CString(CADR(rte2))) == 0 &&
  252.         leftvarno != rightvarno) {    
  253.       /*  Remove the redundent join */
  254.       List temp = MakeTClause();
  255.       CAR(qual) = CAR(temp);
  256.       CDR(qual) = CDR(temp);
  257.       replace_tlist(rightvarno,leftvarno,tlist);
  258.       replace_varnodes(rightvarno,leftvarno,modqual);
  259.     }
  260.       }
  261.     }
  262.     else
  263.       if (and_clause(qual)) 
  264.     foreach(i,get_andclauseargs(qual)) 
  265.       modqual = SemantOpt2(rangetable,CAR(i),modqual,tlist);
  266.       else
  267.     if (or_clause(qual))
  268.       foreach(i,get_orclauseargs(qual))
  269.         modqual = SemantOpt2(rangetable,CAR(i),modqual,tlist);
  270.     else
  271.       if (not_clause(qual))
  272.         modqual = SemantOpt2(rangetable,CDR(qual), modqual,tlist);
  273.  
  274. return(modqual);
  275. }
  276.  
  277. void
  278. replace_tlist(left,right,tlist)
  279.      Index left,right;
  280.      List tlist;
  281. {
  282.   List i = LispNil;
  283.   List tle = LispNil;
  284.   List leftop = LispNil;
  285.   List rightop = LispNil;
  286.  
  287.   foreach(i,tlist) {
  288.     tle = tl_expr(CAR(i));
  289.  
  290.     if (IsA(tle,Var)) {
  291.       if (get_varno((Var)tle) == right) {
  292.     set_varno((Var)tle,left);
  293.     set_varid((Var)tle, lispCons(lispInteger(left),
  294.                 lispCons(CADR(get_varid((Var)tle)),
  295.                      LispNil)) );
  296.       }
  297.     } else
  298.       if (is_clause(tle))
  299.     replace_tlist(left,right,CDR(tlist) );
  300.  
  301.   }
  302.   
  303. }
  304.  
  305. void
  306. replace_varnodes(left,right,qual)
  307.      Index left,right;
  308.      List qual;
  309. {
  310.   List leftop = LispNil;
  311.   List rightop = LispNil;
  312.   List i = LispNil;
  313.  
  314.   if (null(qual));
  315.   if (is_clause(qual)) {
  316.     leftop = (List)get_leftop(qual);
  317.     rightop = (List)get_rightop(qual);
  318.  
  319.     if (IsA(leftop,Var))
  320.       if (get_varno((Var)leftop) == right) {
  321.     set_varno((Var)leftop,left);
  322.     set_varid((Var)leftop, lispCons(lispInteger(left),
  323.                    lispCons(CADR(get_varid((Var)leftop)),
  324.                         LispNil)) );
  325.       } else
  326.     if (IsA(rightop,Var))
  327.       if (get_varno((Var)rightop) == right) {
  328.         set_varno((Var)rightop,left);
  329.         set_varid((Var)rightop, lispCons(lispInteger(left),
  330.                        lispCons(CADR(get_varid((Var)rightop)),
  331.                         LispNil)) );        
  332.       }
  333.   }
  334.   else
  335.     if (and_clause(qual))
  336.       foreach(i,get_andclauseargs(qual)) 
  337.     replace_varnodes(left,right,CAR(i));
  338.     else 
  339.       if (or_clause(qual))
  340.     foreach(i,get_orclauseargs(qual))
  341.       replace_varnodes(left,right,CAR(i));
  342.       else
  343.     if (not_clause(qual))
  344.       replace_varnodes(left,right,CDR(qual));      
  345.       
  346. }
  347. /*
  348.  *  Routine that runs through the tlist and qual pair
  349.  *  and collect all varnos that are not existential.
  350.  *  returns a list of those varnos.
  351.  */
  352.  
  353. List
  354. find_allvars (root,rangetable,tlist,qual)
  355.      List root,rangetable,tlist,qual;
  356. {
  357.   List varlist = LispNil;
  358.   List i = LispNil;
  359.   List tle = LispNil;
  360.   List expr = LispNil;
  361.   int current_nvars;
  362.   int prev_nvars = 0;
  363.  
  364.   if (CAtom(root_command_type_atom(root)) != RETRIEVE) 
  365.     varlist = nappend1(varlist, root_result_relation(root));
  366.   
  367.   foreach(i, tlist) {
  368.     tle = CAR(i);
  369.     expr = tl_expr(tle);
  370.     /*
  371.      *  Assume that each (non const) expr is a varnode by this time.
  372.      */
  373.     if (IsA(expr,Var)) {
  374.       if (!member(lispInteger(get_varno((Var)expr)),varlist))
  375.     varlist = nappend1(varlist, lispInteger(get_varno((Var)expr)));
  376.     }
  377.   }
  378.   current_nvars = length(varlist);
  379.  
  380.   while(current_nvars > prev_nvars) {
  381.     prev_nvars = current_nvars;
  382.     varlist = update_vars(rangetable,varlist,qual);
  383.     current_nvars = length(varlist);
  384.   }
  385.   return(varlist);
  386. }
  387.  
  388. /*
  389.  *  Simply goes through the qual once and
  390.  *  add any new varnos (rels) that participate in a 
  391.  *  join. 
  392.  *  A rel. participates in the query if there is a link back to 
  393.  *  the target relations.
  394.  */
  395.  
  396. List
  397. update_vars(rangetable,varlist,qual)
  398.      List rangetable,varlist,qual;
  399. {
  400.   List leftop;
  401.   List rightop;
  402.   char *attname;
  403.   ObjectId op = 0;
  404.   Index leftvarno = 0;
  405.   Index rightvarno = 0;
  406.   List tmp = LispNil;
  407.  
  408.   if (null(qual))
  409.     return(varlist);
  410.   else 
  411.     if (is_clause(qual)) {
  412.       op = get_opno((Oper)get_op(qual));
  413.       if (!consp(get_leftop(qual))) { /* ignore union vars at this point */
  414.     if (op == 627) {  /* Greg's horrendous not-in op */
  415.       leftvarno = get_varno(get_leftop(qual));
  416.       rightvarno = ConstVarno(rangetable,(Const)get_rightop(qual),&attname);
  417.  
  418.       if (member(lispInteger(leftvarno),varlist)) {
  419.         if (rightvarno != 0 && !member(lispInteger(rightvarno),varlist))
  420.           varlist = nappend1(varlist,lispInteger(rightvarno));
  421.       }
  422.       else
  423.         if (member(lispInteger(rightvarno),varlist))
  424.           if (!member(lispInteger(leftvarno),varlist))
  425.         varlist = nappend1(varlist,lispInteger(leftvarno));    
  426.     } else {
  427.       leftop = (List)get_leftop(qual);
  428.       rightop = (List)get_rightop(qual);
  429.       if (IsA(leftop,Var)) {
  430.         if (IsA(rightop,Var)) {
  431.           if (member(lispInteger(get_varno((Var)leftop)),varlist)) {
  432.         if (!member(lispInteger(get_varno((Var)rightop)),varlist))
  433.           varlist = 
  434.             nappend1(varlist,lispInteger(get_varno((Var)rightop)));
  435.           }
  436.           else
  437.         if (member(lispInteger(get_varno((Var)rightop)),varlist))
  438.           if (!member(lispInteger(get_varno((Var)leftop)),varlist))
  439.             varlist = 
  440.               nappend1(varlist,lispInteger(get_varno((Var)leftop)));
  441.         }
  442.       } /* leftop var */
  443.     } /*else */
  444.       }
  445.     } else  /* is_clause */
  446.       if (and_clause(qual)) {
  447.     foreach(tmp, get_andclauseargs(qual))
  448.       varlist =  update_vars(rangetable,
  449.                  varlist,
  450.                  CAR(tmp));
  451.       }
  452.       else
  453.     if (or_clause(qual)) {
  454.       foreach (tmp, get_orclauseargs(qual))
  455.         varlist = update_vars(rangetable,
  456.                   varlist,
  457.                   CAR(tmp));
  458.     }
  459.     else
  460.       if (not_clause(qual)) 
  461.         varlist = update_vars(rangetable,
  462.                   varlist,
  463.                   get_notclausearg(qual));
  464.  
  465.   return(varlist);
  466. }
  467.  
  468. /*
  469.  *  This routine is necessary thanks to Greg's not-in operator.
  470.  *  Given a const node, routine returns the varno of the relation
  471.  *  referenced or 0 if relation is not in the rangetable.
  472.  */
  473.  
  474. Index
  475. ConstVarno(rangetable,constnode,attname)  
  476.      List rangetable;
  477.      Const constnode;
  478.      char **attname;
  479. {
  480.   static char tmpstring[32];
  481.   char *ptr;
  482.   char *relname;
  483.   List i = LispNil;
  484.   Index position = 0;  /* should be quite safe since varnos start from 1. */
  485.  
  486.   if (!IsA(constnode,Const))
  487.     elog(WARN, "Arg. is not a const node.");
  488.   else {
  489.     ptr = DatumGetPointer(get_constvalue(constnode));
  490.     strcpy (tmpstring, ptr);
  491.     relname = (char *)strtok(tmpstring, ".");
  492.     *attname = (char *)strtok(NULL,"."); 
  493.     
  494.     foreach (i, rangetable) {
  495.       position += 1;
  496.       if (strcmp(relname, CString(CADR(CAR(i)))) == 0) 
  497.     return (position);
  498.     }
  499.   }
  500. return(0);
  501.   
  502. }
  503.  
  504. /*
  505.  *  Routine returns a clause of the form 1=1
  506.  */
  507. List
  508. MakeTClause()
  509. {
  510.   Oper newop;
  511.   Const leftconst;
  512.   Const rightconst;
  513.   ObjectId objid = 96;
  514.   ObjectId rettype = 16;
  515.   int opsize = 0;
  516.   
  517.   newop = MakeOper(objid, InvalidObjectId, 0,rettype,opsize,NULL);
  518.   leftconst = MakeConst(23, 4, Int32GetDatum(1), 0, 1);
  519.   rightconst = MakeConst(23, 4, Int32GetDatum(1), 0, 1);
  520.  
  521.   return(make_opclause(newop,(Var)leftconst,(Var)rightconst));
  522.   
  523. }
  524.  
  525. /*
  526.  *  Routine returns a clause of the form 1=2
  527.  */
  528. List
  529. MakeFClause()
  530. {
  531.   Oper newop;
  532.   Const leftconst;
  533.   Const rightconst;
  534.   ObjectId objid = 96;
  535.   ObjectId rettype = 16;
  536.   int opsize = 0;
  537.   
  538.   newop = MakeOper(objid, InvalidObjectId, 0,rettype,opsize,NULL);
  539.   leftconst = MakeConst(23, 4, Int32GetDatum(1), 0, false);
  540.   rightconst = MakeConst(23, 4,Int32GetDatum(2), 0, false);
  541.  
  542.   return(make_opclause(newop,(Var)leftconst,(Var)rightconst));
  543.   
  544. }
  545.